package leetcode101.tree;

import java.util.Arrays;

/**
 * @author Synhard
 * @version 1.0
 * @class Code21
 * @description 889. 根据前序和后序遍历构造二叉树
 * 返回与给定的前序和后序遍历匹配的任何二叉树。
 *
 *  pre 和 post 遍历中的值是不同的正整数。
 *
 *  
 *
 * 示例：
 *
 * 输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
 * 输出：[1,2,3,4,5,6,7]
 *  
 *
 * 提示：
 *
 * 1 <= pre.length == post.length <= 30
 * pre[] 和 post[] 都是 1, 2, ..., pre.length 的排列
 * 每个输入保证至少有一个答案。如果有多个答案，可以返回其中一个。
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-06-27 7:20
 */
public class Code21 {

    public static void main(String[] args) {

    }

    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        if (pre.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(pre[0]);
        if (pre.length == 1) {
            return root;
        }
        int counter = 0;
        for (int j : post) {
            if (pre[1] != j) {
                counter++;
            } else {
                break;
            }
        }
        root.left = constructFromPrePost(Arrays.copyOfRange(pre, 1, counter + 2), Arrays.copyOfRange(post, 0, counter + 1));
        root.right = constructFromPrePost(Arrays.copyOfRange(pre, counter + 2, pre.length), Arrays.copyOfRange(post, counter + 1, post.length));
        return root;
    }

}
